package com.liuzhilong.infrastructure.framework.algorithms.datastruct.tree;

import java.util.*;
import java.util.function.Consumer;

/**
 * 二叉树
 * @author longandai@163.com
 */
public class BinaryTree {
    /**
     * 遍历并打印一个node 按照如下格式进行打印操作
     *  <pre>
     *     A
     *    / \
     *   B   C
     *  / \  /\
     * D  E F  G
     *  </pre>
     * @param node
     */
    public void print(Node node){

    }



    /**
     * 二叉树的构建模型<br>
     * 简单构建，不考虑平衡性
     * @param data
     * @return
     */
    public Node simpleBuild(int ... data){
        if(data.length==0){
            return null;
        }
        Node root = new Node();
        root.data = data[0];
        for (int i = 1; i < data.length; i++) {
            loopSimpleBuildSetData(root,data[i]);
        }
        return root;
    }

    private void loopSimpleBuildSetData(Node node, int data) {
        boolean isLeft = node.data>data;
        if (isLeft) {
            if (node.left!=null) {
                loopSimpleBuildSetData(node.left,data);
            }else {
                Node newNode = new Node();
                newNode.data = data;
                node.left = newNode;
            }
        }else {
            if (node.right!=null) {
                loopSimpleBuildSetData(node.right,data);
            }else {
                Node newNode = new Node();
                newNode.data = data;
                node.right = newNode;

            }
        }

    }




    /**
     * <h2>二叉树的锯齿形层序遍历</h2>
     * <p>
     *     给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
     *     <pre>
     * 例如：
     * 给定二叉树[3,9,20,null,null,15,7],
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回锯齿形层序遍历如下：
     *
     * [
     *   [3],
     *   [20,9],
     *   [15,7]
     * ]
     *
     *     </pre>
     * </p>
     * <h2>思路</h2>
     * 利用广度优先算法的思路，结合stack数据结构，按照分层进行遍历。每层变化读取方向，并返回每层的结果
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(Node root) {

        List<List<Integer>> result =new LinkedList<>();
        if(root==null){
            return result;
        }
        //变形的广度优先遍历
        //采用栈的方式进行每层的遍历
        Deque<Node> deque = new LinkedList();
        deque.push(root);
        // deque.poll();
        boolean directLeft=true;
        while(true){
            Deque<Node> nextLevel = new LinkedList();
            List<Integer> resultLevel = new LinkedList<>();
            while(!deque.isEmpty()){
                Node node =deque.pop();
                resultLevel.add(node.data);
                if(directLeft){
                    if(node.left!=null){
                        nextLevel.push(node.left);
                    }
                    if(node.right!=null){
                        nextLevel.push(node.right);
                    }

                }else {

                    if(node.right!=null){
                        nextLevel.push(node.right);
                    }
                    if(node.left!=null){
                        nextLevel.push(node.left);
                    }
                }
            }
            result.add(resultLevel);
            if(nextLevel.isEmpty()){
                break;
            }
            directLeft=!directLeft;
            deque = nextLevel;
        }
        return result;
    }


    /**
     * 节点信息
     */
    private static class Node{
        int data;
        Node left;
        Node right;
    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        //构建简单的树结构
        int[] data = new int[]{3,1,6,23,7,98,4,20};
        Node node =binaryTree.simpleBuild(data);
        //测试dsf
        System.out.println();
        System.out.println(">>>>>>>>>>>DFS<<<<<<<<<<<<");
        BinaryTreeErgodic.dfs(node,item->System.out.print(item.data+" "));
        //测试广度优先
        System.out.println();
        System.out.println(">>>>>>>>>>>BFS<<<<<<<<<<<<");
        BinaryTreeErgodic.bfs(node,item->System.out.print(item.data+" "));
        //测试中序遍历
        System.out.println();
        System.out.println(">>>>>>>>>>>MOT<<<<<<<<<<<<");
        BinaryTreeErgodic.midOrderTraverse(node,item->System.out.print(item.data+" "));
    }

    /**
     * <h1>二叉树的遍历方式</h1>
     * 二叉树的遍历方式，通常分为5种。
     *
     * @author longandai@163.com
     */
    private static class BinaryTreeErgodic{
        /**
         * <h2>深度优先遍历（Depth-First-Search）</h2>
         * <p>
         *  给定结构
         *  <pre>
         *     A
         *    / \
         *   B   C
         *  / \  /\
         * D  E F G
         * </pre>
         * 遍历顺序为先根节点、再左子树、再又子树
         * </p>
         * <p>
         *     <h2>实现方式：</h2>Deuqe
         *     利用stack数据结构，后进先出的原理。每次访问的时候先把右子树压入栈，再把左子树压入栈。
         * </p>
         * @param root
         */
        public static void   dfs(Node root, Consumer<Node> consumer){
            //此时使用deque来作为stack,之所以不使用Stack类，是因为Deque要比stack类的效率高不少
            //设计到的方法
            //deque.push(null);
            //deque.pull();
            Deque<Node> deque = new LinkedList();
            deque.push(root);
            while(!deque.isEmpty()){
                //弹出
                Node node = deque.pop();
                consumer.accept(node);
                //先压入右侧，再压入左侧
                if (node.right != null) {
                    deque.push(node.right);
                }
                if (node.left != null) {
                    deque.push(node.left);
                }
            }



        }

        /**
         * 广度优先遍历(Breadth-First-Search)
         * <p>
         *  给定结构
         *  <pre>
         *     A
         *    / \
         *   B   C
         *  / \  /\
         * D  E F G
         * </pre>
         * BFS是从根节点开始，沿着树的宽度遍历树的节点
         * </p>
         * <h2>实现方式</h2>
         * 使用队列来实现。访问每个节点的时候，把node压入队列
         */
        public static void bfs(Node root, Consumer<Node> consumer) {
            //依然是用Deque来作为队列。Deque 支持stack和quque两种数据结构语法。
            // 使用的api
            //  deque.offer(root);
            //  deque.poll();
            Deque<Node> deque = new LinkedList();
            deque.offer(root);
            while (!deque.isEmpty()){
                Node node = deque.poll();
                consumer.accept(node);
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
        }

        /**
         * <h2>二叉树遍历-中序遍历</h2>
         * 前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树（根->左->右）
         * <p></p>
         * @param root
         * @param consumer
         */
        public static void preOrderTraverse(Node root, Consumer<Node> consumer){
            consumer.accept(root);
            if(root.left!=null){
                preOrderTraverse(root.left,consumer);
            }
            if(root.right!=null){
                preOrderTraverse(root.right,consumer);
            }
        }
        /**
         * <h2>二叉树遍历-中序遍历</h2>
         * 中序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树（左->根->右）
         * <p></p>
         * @param root
         * @param consumer
         */
        public static void midOrderTraverse(Node root, Consumer<Node> consumer){

            if(root.left!=null){
                midOrderTraverse(root.left,consumer);
            }
            consumer.accept(root);
            if(root.right!=null){
                midOrderTraverse(root.right,consumer);
            }
        }
        /**
         * <h2>二叉树遍历-后序遍历</h2>
         * 后序遍历：首先遍历左子树，然后遍历右子树，最后访问根节点（左->右->根）
         * <p></p>
         * @param root
         * @param consumer
         */
        public static void postOrderTraverse(Node root, Consumer<Node> consumer){

            if(root.left!=null){
                postOrderTraverse(root.left,consumer);
            }
            if(root.right!=null){
                postOrderTraverse(root.right,consumer);
            }
            consumer.accept(root);
        }
    }
}
